package datastructure.structure;


import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author or2
 * @date 2021/8/5 18:07
 */
public class MaxHeap<E extends Comparable<E>> {

    private ArrayList<E> arrayList;

    MaxHeap() {
        arrayList = new ArrayList<>();
    }

    /**
     * 初始化堆容量
     *
     * @param capacity 堆的初始容量
     */
    MaxHeap(int capacity) {
        arrayList = new ArrayList<>(capacity);
    }

    /**
     * 返回堆的大小
     *
     * @return 当前元素个数
     */
    public int size() {
        return arrayList.size();
    }

    /**
     * 当前堆是否为空
     *
     * @return 不为空 -> true<br/>为空 -> false
     */
    public boolean isEmpty() {
        return arrayList.isEmpty();
    }

    /**
     * 返回该索引的元素的父元素的索引
     *
     * @param index 元素索引
     * @return 其父元素的索引
     */
    private int parent(int index) {
        if (index == 0) {
            throw new ArrayIndexOutOfBoundsException("该节点无父元素");
        }

        return index - 1 >> 1;
    }

    /**
     * 返回该元素的索引的左孩子的索引
     *
     * @param index 元素索引
     * @return 其左孩子的索引
     */
    private int liftChild(int index) {
        return (index << 1) + 1;
    }

    /**
     * 返回该元素的索引的右孩子的索引
     *
     * @param index 元素索引
     * @return 其右孩子的索引
     */
    private int rightChild(int index) {
        return index + 1 << 1;
    }

    /**
     * 插入一个新元素
     *
     * @param value 新元素的值
     */
    public void add(E value) {
        arrayList.add(value);
        siftUp(arrayList.size() - 1);
    }

    /**
     * 检查当前元素, 上浮整理堆
     *
     * @param index 检查元素的下标
     */
    private void siftUp(int index) {
        if (index == 0) {
            return;
        }
        E cur = arrayList.get(index);
        int parentIndex = parent(index);
        E parent = arrayList.get(parentIndex);

        if (parent.compareTo(cur) < 0) {
            arrayList.set(index, parent);
            arrayList.set(parentIndex, cur);
            siftUp(parentIndex);
        }
    }

    /**
     * 返回当前堆中最大的元素
     *
     * @return
     */
    public E getMax() {
        return arrayList.get(0);
    }

    /**
     * 获取当前最大元素, 并删除
     *
     * @return 当前最大元素
     */
    public E popMax() {
        E max = getMax();
        int last = arrayList.size() - 1;
        arrayList.set(0, arrayList.get(last));
        arrayList.remove(last);

        siftDown(0);

        return max;
    }

    /**
     * 下沉当前元素使堆符合定义
     *
     * @param index 当前元素索引
     */
    private void siftDown(int index) {

        int liftChild;
        while (true) {
            liftChild = liftChild(index);
            if (liftChild >= size() - 1) {
                break;
            }

            int p = liftChild;
            int rightChild = rightChild(index);
            if (rightChild < size() && arrayList.get(rightChild).compareTo(arrayList.get(liftChild)) > 0) {
                p = rightChild;
            }

            E cur = arrayList.get(index);
            E pMax = arrayList.get(p);
            if (cur.compareTo(pMax) > 0) {
                break;
            }

            arrayList.set(index, pMax);
            arrayList.set(p, cur);
            index = p;
        }
    }

    public static <E extends Comparable<E>> MaxHeap<E> of(E[] arr) {
        int length = arr.length;
        MaxHeap<E> maxHeap = new MaxHeap<>(length);
        maxHeap.arrayList.addAll(Arrays.asList(arr));
        for (int i = maxHeap.parent(length - 1); i >= 0; i--) {
            maxHeap.siftDown(i);
        }

        return maxHeap;
    }
}
